package s7_查找算法.search3_插值查找;

import s6_排序算法.BaseSort;
import s6_排序算法.sort1_交换排序.QuickSort;
import s7_查找算法.BaseSearch;

import java.util.Arrays;

/**
 * <code>{@link InsertValueSearch}</code>
 * <p>
 * description: Search
 * <p>
 *
 * @author 西瓜瓜 on 2022/2/21 21:31
 * 插值查找
 * 1.类似二分查找，不同的是插值查找每次从自适应mid处开始查找
 * 2.midIndex= low + (high-low)*(key-arr[low])/(arr[high]-arr[low]) // 插值索引 low:最小值索引  high：最大值索引  arr：数组  key：待查找元素
 */
public class InsertValueSearch extends BaseSearch {

    public static void main(String[] args) {
        int[] arr = BaseSort.normal();
        System.out.println(Arrays.toString(arr));
        new QuickSort().asc(arr);
        System.out.println(Arrays.toString(arr));


        int target = 2;
        int search = new InsertValueSearch().search(arr, target);
        System.out.println(search);
    }

    @Override
    public int search(int[] arr, int target) {
        int left =0, right=arr.length-1;
        return search(arr, target, left, right);
    }

    private int search(int[] arr, int target, int left, int right) {
        if(left > right) return -1;
        int mid = left + (right-left)*(target-arr[left])/(arr[right]-arr[left]);
        if(arr[mid] == target) return mid;
        if(arr[mid] > target) {
            return search(arr, target, left, mid-1);
        } else {
            return search(arr, target, mid+1, right);
        }
    }
}
